//
// Description: Dijkstra算法模板
// Created by Loading on 2021/8/28.
//

// 例题：https://www.acwing.com/problem/content/description/851/

/* 适用于在带权有向图中求解 1 号点（起点）到任意点之间的最短路径，注意：权值不可为负，因为这样将不存在最短路 */

/*
 * 算法思想：Dijkstra最朴素的思想就是按长度递增的次序产生最短路径。
 * 即每次对所有可见点的路径长度进行排序后，选择一条最短的路径，这条路径就是对应顶点到源点的最短路径。
 */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
// 数据范围
constexpr int N = 501; // 稀疏图数据范围为 1e5 左右
// 路径权重极大值
constexpr int INF = 0x3f3f3f3f;

int g[N][N];  // 邻接矩阵存储每条边（适用于稠密图）
int h[N], e[N], ne[N], w[N], idx; // 邻接表存储每条边（适用于稀疏图）

int dist[N];  // 存储 1 号点到每个点的最短距离
bool status[N];   // 存储每个点的最短路是否已经确定

int n; // 节点数

/* 朴素Dijkstra，时间复杂度：O(n^2 + m), n 表示点数，m 表示边数 */
// 求 1 号点到 n 号点的最短路，如果不存在则返回 -1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 一共有 n - 1 个点的最短路待确定
    for (int i = 0; i < n - 1; i++) {
        int t = -1;
        // 在还未确定最短路的点中，寻找到起点距离最小的点，第一次寻找时，这个点是 1
        for (int j = 1; j <= n; j++) {
            if (!status[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        // 1 到 t 的最短路径已经得出，用 t 更新其他点的距离
        // 1 到 j 的距离，与 1 到 t 再加上 t 到 j 的距离，取最小（松弛操作）
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }

        // t 确定最短路
        status[t] = true;
    }

    return dist[n] == INF ? -1 : dist[n];
}

/* 堆优化版Dijkstra，时间复杂度：O(mlogn)，n 表示点数，m 表示边数 */
// 求 1 号点到 n 号点的最短路，如果不存在则返回 -1
int dijkstra_heap() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 小根堆，first存储距离，second存储节点编号
    priority_queue<PII, vector<PII>, greater<>> heap;
    heap.push({0, 1});
    while (!heap.empty()) {
        // 取堆顶元素，记录距离 1 号点最近的点的距离和编号
        auto t = heap.top();
        heap.pop();

        int v = t.second, d = t.first;
        // 如果此点已经被确认过最短距离，则忽略
        if (status[v]) {
            continue;
        }
        status[v] = true;
        // 更新其他点的距离
        for (int i = h[v]; i != -1; i = ne[i]) {
            int j = e[i];
            // 松弛操作
            if (dist[j] > d + w[i]) {
                dist[j] = d + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    return dist[n] == INF ? -1 : dist[n];
}

// 邻接表增加边，a 到 b 有一条权重为 c 的边
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int main() {

    return 0;
}